# 作者： 李泉志
# 2025年01月12日20时21分秒
# 2947029073@qq.com

class Node:
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild


class BinaryTree:
    def __init__(self):
        self.root = None
        self.help_queue = []  # 辅助队列

    def level_build_tree(self, node: Node):
        if self.root is None:
            self.root = node
            self.help_queue.append(node)
        else:
            self.help_queue.append(node)
            if self.help_queue[0].lchild is None:
                self.help_queue[0].lchild = node
            else:
                self.help_queue[0].rchild = node
                self.help_queue.pop(0)

    def pre_order(self, cur_node: Node):
        if cur_node is not None:  # if cur_node:
            print(cur_node.elem, end=' ')
            self.pre_order(cur_node.lchild)
            self.pre_order(cur_node.rchild)


    def in_order(self, cur_node: Node):
        if cur_node:
            self.in_order(cur_node.lchild)
            print(cur_node.elem, end=' ')
            self.in_order(cur_node.rchild)

    def post_order(self, cur_node: Node):
        if cur_node:
            self.post_order(cur_node.lchild)
            self.post_order(cur_node.rchild)
            print(cur_node.elem, end=' ')


    # 广度优先遍历
    def breadth_first_traversal(self):
        help_queue = []
        help_queue.append(self.root)
        while help_queue:
            cur_node = help_queue.pop(0)
            print(cur_node.elem, end=' ')
            if cur_node.lchild:
                help_queue.append(cur_node.lchild)
            if cur_node.rchild:
                help_queue.append(cur_node.rchild)


if __name__ == '__main__':
    tree = BinaryTree()
    for i in range(1, 11):
        new_node = Node(i)
        tree.level_build_tree(new_node)  # 结点放入树中
    tree.pre_order(tree.root)  # 先序遍历=深度
    print()
    tree.in_order(tree.root)  # 中序遍历
    print()
    tree.post_order(tree.root)  # 后序遍历
    print()
    tree.breadth_first_traversal()  # 广度优先遍历
    print()